package com.leetcode.砝码问题;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 问题：给定一组砝码，求出可以称出几种不同的重量，砝码可放置天平两端。
 * 例如：[1,4] 可以称出 1，3，4，5三种不同的重量（3=4-1；5=4+1）
 * 方法：
 * 规定砝码放在左边为正（加），放在右边为负（减）
 * 所以砝码有三种状态：放左边、不放、放右边
 * 用一个Set集合存放可称出的多有重量，Set先存第一个砝码的重量，表示可以称该重量，再存一个0，表示第一个砝码不放
 * 接下来每一个砝码要做的操作：
 * 1.放左边：需要加上Set里边所有的元素，然后存入Set中
 * 2.不放：第二个砝码开始，如果不放，相当于没有这颗砝码，可不进行操作
 * 2.放右边：需要让Set里边的元素减去该砝码，得到是重量存入Set中
 * 以上3个步骤，如果第1步有添加，则第3步遍历Set中所有元素是不包括第1步所添加的
 * 随后，再将0删除（0这里只是辅助作用，表示前面的砝码没有放）
 */
public class Weights {
    public static void main(String[] args) {
        int[] w = new int[]{1};
        Set<Integer> cnt = weightsCount(w);
        System.out.println("砝码为：" + Arrays.toString(w));
        System.out.println("可称出一下重量：");
        if (cnt != null) {
            for (Integer weights : cnt) {
                System.out.print(weights + " ");
            }
        }
    }

    public static Set<Integer> weightsCount(int[] W) {
        if (W.length == 0) {
            return null;
        }
        Set<Integer> cnt = new HashSet<>();
        cnt.add(W[0]);
        cnt.add(0);
        for (int i = 1; i < W.length; i++) {
            //获取砝码
            int weights = W[i];
            //将Set转为数组，遍历数组相当于遍历添加之前的Set，之后Set添加就不会影响到
            Object[] W_Cnt = cnt.toArray();
            for (Object o : W_Cnt) {
                //获取之前可以称出的重量情况
                int temp = (int) o;
                //选左
                if (temp + weights > 0) {
                    cnt.add(temp + weights);
                } else {
                    cnt.add(Math.abs(temp + weights));//只存正数，负数表示天平右边的砝码重于左边
                }

                //不选
                //不执行操作

                //选右
                if (temp - weights > 0) {
                    cnt.add(temp - weights);
                } else {
                    cnt.add(Math.abs(temp - weights));
                }
            }
        }
        cnt.remove(0);
        return cnt;
    }
}
